// 二叉树的最近公共祖先
var lowestCommonAncestor = function (root, p, q) {
  let ans
  const dfs = (root, p, q) => {
    if (root === null) return
    const l = dfs(root.left, p, q)
    const r = dfs(root.right, p, q)
    if ((l && r) || ((root.val === p.val || root.val === q.val) && (l || r))) {
      ans = root
    }
    return l || r || root.val === p.val || root.val === q.val
  }

  dfs(root, p, q)

  return ans
}
// 方法 2
var lowestCommonAncestor = function (root, p, q) {
  if (root === null || root === p || root === q) return root
  let left = lowestCommonAncestor(root.left, p, q)
  let right = lowestCommonAncestor(root.right, p, q)
  return left === null ? right : right === null ? left : root
}
